package 蓝桥._2024.砍柴;

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int T = scan.nextInt();
        int[] lens = new int[T];
        for (int i = 0; i < T; i++) {
            lens[i] = scan.nextInt();
        }
        // 素数筛
        int max = 100010;
        boolean[] isPrime = new boolean[max];
        for (int i = 2; i < max; i++) {
            isPrime[i] = true;
        }
        for (int i = 2; i < max; i++) {
            if (isPrime[i]) {
                for (int j = i + i; j < max; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 小于当前数的最大素数
        int[] maxPrime = new int[max];
        int lastPrime = 2;
        for (int i = 2; i < max; i++) {
            if (isPrime[i]) {
                maxPrime[i] = i;
                lastPrime = i;
            } else {
                maxPrime[i] = lastPrime;
            }
        }
        for (int i = 0; i < T; i++) {
            int len = lens[i];
            int total = 0;
            while (len > 1){
                int p = maxPrime[len];
                len -= p;
                total++;
            }
            if(total % 2 == 0){
                System.out.println("0");
            }else{
                System.out.println("1");
            }
        }
        scan.close();
    }
}